package problems.daily.y2022m8;

import java.util.ArrayList;
import java.util.List;

/**
 * 761. 特殊的二进制序列
 * https://leetcode.cn/problems/special-binary-string/
 *
 * @author habitplus
 * @since 2022/8/8 13:39
 */
public class D20220808_761 {
    public String makeLargestSpecial(String s) {
        if (s.length() < 2) return s;

        int count = 0;
        int l = 0;
        int n = s.length();
        List<String> subs = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '1') {
                ++count;
            } else {
                --count;
                if (count == 0) {
                    subs.add("1" + makeLargestSpecial(s.substring(l + 1, i)) + "0");
                    l = i + 1;
                }
            }
        }

        subs.sort((s1, s2) -> s2.compareTo(s1));
        StringBuffer buffer = new StringBuffer();
        for (String str : subs) {
            buffer.append(str);
        }

        return buffer.toString();
    }
}
